package 剑指Offer;

import java.util.PriorityQueue;
import java.util.Queue;

public class Offer41_数据流中的中位数 {
    class MedianFinder {
        Queue<Integer> A, B;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
            B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
        }

        // 维持堆数据平衡，并保证小顶堆的最小值大于或等于右边堆的最大值
        public void addNum(int num) {
            // N 为 奇数：需向 B 添加一个元素。实现方法：将新元素 num插入至 A ，再将 A堆顶元素插入至 B ；
            if (A.size() != B.size()) {
                A.add(num);
                B.add(A.poll());
            } else {//当 m = n（即 N 为 偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B ，再将 B 堆顶元素插入至 A ；
                B.add(num);
                A.add(B.poll());
            }
        }

        public double findMedian() {
            //A.size() != B.size()相当是奇数，如果是偶数A,B的长度应该相同
            return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
        }
    }

}
